import math


def get_intersection(border, k, b):
    close = 3
    no_close = 30
    # 找到所有精度满足要求的点
    points = []
    for x, y in border:
        if _get_distance((x, y), k, b) < close:
            points.append((x, y))
    # 将这些点划分为若干聚类
    point_sets = _clustering(points, no_close)
    # 从每个聚类中选出最优的一个点作为交点
    target_points = _opt(point_sets, k, b, close)
    # 再运行两次聚类和最优化算法
    for i in range(0, 2):
        point_sets = _clustering(target_points, no_close)
        target_points = _opt(point_sets, k, b, close)
    return target_points


# 聚类算法
def _clustering(points, no_close):
    point_sets = []
    for x, y in points:
        if point_sets:
            is_find = False
            for point_set in point_sets:
                x_mean = _get_x_mean(point_set)
                y_mean = _get_y_mean(point_set)
                if math.fabs(x_mean - x) > no_close or math.fabs(y_mean - y) > no_close:
                    continue
                else:
                    is_find = True
                    point_set.append((x, y))
                    break
            if not is_find:
                point_sets.append([(x, y)])
        else:
            point_sets.append([(x, y)])
    return point_sets


# 选择最优点
def _opt(point_sets, k, b, close):
    target_points = []
    for point_set in point_sets:
        curr_min = close
        target_point = None
        for x, y in point_set:
            if _get_distance((x, y), k, b) < curr_min:
                curr_min = _get_distance((x, y), k, b)
                target_point = (x, y)
        target_points.append(target_point)
    target_points.sort(key=lambda p: p[0])
    return target_points


# 求某个点集x坐标的均值
def _get_x_mean(points):
    x_sum = 0
    for x, y in points:
        x_sum += x
    return x_sum / len(points)


# 求某个点集y坐标的均值
def _get_y_mean(points):
    y_sum = 0
    for x, y in points:
        y_sum += y
    return y_sum / len(points)


# 点到直线的距离
def _get_distance(point, k, b):
    x, y = point
    return math.fabs(k * x + b - y) / math.sqrt(1 + math.pow(k, 2))
